Programming languages can use patterns to distinguish among classes of values. For example, the following two lines of pseudo-code define a function that computes the sum of a list of integers.
Sum(nil) = 0;Sum(cons[head,tail]) = head+Sum(tail);
The patterns in this example serve two purposes. First, they distinguish among input cases. Second, they enable concise value deconstruction through the use of pattern variables and type inference.
Patterns are closely related to structural types. The regular tree patterns described herein are regular tree types that may also include variable bindings. A tree pattern coupled with a semantic action is called a tree transformation rule.
Structural type systems, such as XML schema languages, define categories of values. Programming languages often use structural type systems to statically check program safety properties. SQL databases also use a type system that is primarily focused on structure. Tables that result from joins, for example, contain tuples that can be described as having an anonymous structural type. Database management systems require that a variety of programs can interpret the data stored in the system. Structural type systems help database management systems meet this requirement.
Distributed systems also induce a requirement for structural types. Due to latency, messages exchanged among distributed program components are often larger and more complex than method parameters exchanged among objects.
The values stored in databases and exchanged among distributed components are intermediate in complexity between the simple values manipulated by program expressions and the complexity of a Turing Machine. Described herein, regular tree patterns are used to define these intermediate levels of structural complexity.
Expressing and analyzing both ordered and unordered regular tree patterns would be useful and beneficial abilities. Examples of domains in which analysis would beneficially be improved include model checking and authorization logic which uses partially-ordered tree patterns. Certain existing languages, such as XML schema, may use partially ordered regular trees but currently lack a means for sub-typing. Further, such languages may impose semantic restrictions in order to support efficient implementation under currently known methods.
Some work on greedy regular expression matching and the programming language XStatic has explored how to incorporate regular ordered tree types into object-oriented languages. Like XDuce, XStatic uses a uniform representation for sequences. Such work maps regular ordered tree types to objects, but uses flattening to support the natural semantics of regular language inclusion. Finally, trx explores regular ordered tree types in the context of Scheme.
Some work has also been accomplished on pushdown forest automata (PFAs). However, PFAs do not provide a sub-typing algorithm or a mechanism for addressing unordered nests (multisets).